package Stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 *   题目：设计一个支持增量操作的栈
 *   题目详述 ：
 * 请你设计一个支持下述操作的栈。
 * 实现自定义栈类 CustomStack
 *
 * CustomStack(int maxSize)：用 maxSize 初始化对象，maxSize 是栈中最多能容纳的元素数量，栈在增长到 maxSize 之后则不支持 push 操作。
 * void push(int x)：如果栈还未增长到 maxSize ，就将 x 添加到栈顶。
 * int pop()：弹出栈顶元素，并返回栈顶的值，或栈为空时返回 -1 。
 * void inc(int k, int val)：栈底的 k 个元素的值都增加 val 。如果栈中元素总数小于 k ，则栈中的所有元素都增加 val 。
 *
 */
public class P1381{
    /**
     *  核心思想 ：（使用主栈和辅助栈，辅助栈主要用于increment操作）
     *  push,pop方法的时间复杂度 ：O（1）
     *  increment方法的时间复杂度 ：O（n）
     *  其空间复杂度 ：O（n）
     */
//    private int maxSize;
//    private int size;
//    Deque<Integer> stack,helpStack;
//    public P1381(int maxSize) {
//        // 初始化maxSize对象
//        this.maxSize = maxSize;
//        this.size = 0;
//        // 初始化栈（使用主站 和 辅助栈[辅助栈用于将栈反转，同时实现功能increment方法]）
//        stack = new LinkedList<>();
//        helpStack = new LinkedList<>();
//    }
//
//    public void push(int x) {
//        // 如果（1）栈为空（2）栈中元素未满，直接将元素插入主栈
//        if(stack.isEmpty() || size < maxSize){
//            size++;
//            stack.push(x);
//        }
//        // 若是栈中不为空，同时栈中元素已经满了，===》即，不用向栈中插入此元素
//    }
//
//    public int pop() {
//        // 当栈不为空时，直接将栈顶元素弹出即可
//        if(!stack.isEmpty()){
//            size--;
//            return stack.pop();
//        }
//        // 若是未进入上述的if语句的话，说明栈为空，直接返回-1即可；
//        return -1;
//    }
//
//    public void increment(int k, int val) {
//        while(!stack.isEmpty()){ // 循环结束条件 ：主栈为空1
//            // 将主栈中的所有元素，弹出并且将其压入辅助栈中
//            helpStack.push(stack.pop());
//        }
//        if(k >= size){
//            // 当k的值大于等于栈中元素的个数，直接将辅助栈中的元素 + val插入到主栈中去
//            while(!helpStack.isEmpty()){
//                stack.push(helpStack.pop() + val);
//            }
//        }
//        else {
//            // 当k的值小于栈中元素的个数，直接将辅助栈中前k个元素 + val插入到主栈中去
//            for(int i = 0;i < k ;i++){
//                stack.push(helpStack.pop() + val);
//            }
//            while(!helpStack.isEmpty()){
//                stack.push(helpStack.pop());
//            }
//        }
//    }

    /**
     *  核心思想 ：（使用数组，来模拟栈结构）
     *   push,pop方法的时间复杂度 ：O（1）
     *   increment方法的时间复杂度 ：O（n）
     *   由于使用了辅助数组stack，其空间复杂度 ：O（maxSize）
     */
    private int[] stack; // 使用数组模拟栈结构(数组从1开始存储元素)
    private int[] add; // 使用辅助数组
    private int size;
    public P1381(int maxSize) {
        stack = new int[maxSize + 1];
        add = new int[maxSize + 1];
        size = 0;
    }

    public void push(int x) {
        if(size < stack.length - 1){
            size++;
            stack[size] = x;
        }
    }

//    public int pop() {
//        if(size == 0){
//            return -1;
//        }
//        size--;
//        return stack[size]; // 注意 ：由于数组是0开始的，所以我们需要更加进一步地注意数组的边界（防止索引超出数组的边界）
//    }
//
//    public void increment(int k, int val) {
////        int number = k > size ? size : k;
//        int number = Math.min(k, size);
//        for(int i = 0 ;i < number ; i++){
//            stack[i] += val;
//        }
//    }
    /**
     * 此处的时间复杂度为 ：O（k）
     *     优化方案 ；
     *     即，使用辅助数组add，调用increment方法来由于从栈底开始的k个元素 + val
     *     ===》 即，由于栈中k个元素都是增加val，所以我们只需要在辅助数组的add[k - 1]位置存储val值；
     *     其值的传递 ：在于调用pop方法，将栈顶元素所对应的辅助数组 add[栈顶元素索引]，累加到下一个栈顶元素的辅助数组对应的值
     */
    public int pop() {
        if (size == 0) {
            return -1;
        }
        int result = stack[size] + add[size];
        if(size != 1){
            add[size -1] += add[size];
        }
        add[size] = 0;
        --size;
        return result;
    }

    public void increment(int k, int val) {
        int minValue = Math.min(k, size);
        add[minValue] += val;
    }

}
